package com.itheima.datastructure.binarysearchtree.binarytree;

import com.itheima.datastructure.stack.LinkedListStack;

//统一模板处理前中后遍历
public class E03Leetcode145_2 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(new TreeNode(new TreeNode(4),2,null),
                1,new
                TreeNode(new TreeNode(5),3,new TreeNode(6))
        );
        LinkedListStack<TreeNode> stack=new LinkedListStack<>(1000);

        TreeNode curr=root;//当前节点
        TreeNode pop=null;//最近一次弹出栈的元素
        while(!stack.isEmpty() || curr!=null){
            if(curr!=null){
                stack.push(curr);
                //待处理的左子树
                colorPrintln("前："+curr.val,31);
                curr=curr.left;
            }else{
                TreeNode peek=stack.peek();
                //没有右子树
                if(peek.right==null){
                    colorPrintln("中："+peek.val,36);
                    pop=stack.pop();
                    colorPrintln("后："+pop.val,34);
                }
                //右子树处理完成
                else if (peek.right==pop) {
                    pop=stack.pop();
                    colorPrintln("后："+pop.val,34);
                }
                //待处理的右子树
                else{
                    colorPrintln("中："+peek.val,36);
                    curr=peek.right;
                }
            }
        }

    }
    private static void colorPrintln(String origin,int color){
        System.out.printf("\033[%dm%s\033[0m%n",color,origin);
    }
}
